Microprocessors, such as general purpose microprocessors, digital signal processors, and the like, typically include an arithmetic logic unit ("ALU") and a set of registers, sometimes referred to as general purpose registers ("GPRs"), where the operands to be operated on by the ALU can be accessed by the ALU, either immediately or one or more cycles later, in an ALU operation, and where the results of ALU operations can be immediately stored in an ALU operation.
In addition to the operations of addition and subtraction, ALUs may also have the capability of performing Boolean operations, such as compare, logical OR, bitwise OR, AND, or the like. The results of such operations, Boolean values, are typically stored in a register separate from the GPRs, for example in a status register. However, the Boolean values thus stored are not as accessible to the ALU as values stored in a GPR. In other words, more processor cycles are needed to, for example, to present such Boolean values to the ALU as an input, should it be desired to do so, as compared with presenting a GPR value as an input to the ALU, which is typically done in the same clock cycle in which the ALU operation is performed.
Nonetheless, it has been discovered that in some operations executed in microprocessors processing efficiencies can be realized by the exploitation of certain inventive advances applied to the microprocessor architecture, as disclosed hereinbelow.
One such operation arises in the execution of code implementing convolutional coding. Convolutional coding is a technique that has been used for a number of years, particularly in the form of Viterbi coding, in the area of transmission and reception of digital data. See, for example, The Principles of Digital Communication and Coding, by Andrew J. Viterbi and Jim K. Omura, published by McGraw-Hill in 1979, and "The Viterbi Algorithm," by G. David Forney, Jr., Proc. IEEE, V. 61, No. 3, pp. 268-278, March 1973. The Viterbi coding technique is widely used as a forward error correction technique for removing noise from digital radio signals.
Basically, convolutional codes are codes generated from a stream of digital data wherein the data is convoluted by being operated on by generator polynomials, the operations being performed modulo 2. Encoding can be regarded as being performed with respect to a finite number of internal states specific to the encoder. These states and the transitions between them can be represented in the form of a trellis. A path within such trellis represents an encoded sequence, analogous to a code word. Encoding a digital bit stream therefore involves crossing the trellis along one possible path, each new bit of the stream of information determining a branch in the path an causing the simultaneous transmission of code bits relating to the path followed.
The code bits are transmitted through a transmission medium to a receiver and an associated decoder. The transmission medium will, in general, have properties such as noise, interference, jamming, etc., that prevent the receiver from receiving the code bits error free. Decoding at the receiving end, therefore, involves taking the received stream of code bits and reconstructing the trellis path taken by the encoder at the transmitting end in generating the code bits, so as to thereby recover the sequence of information bits that caused such path to be selected in the encoding process. This, in turn, involves, first, reconstruction of the trellis, second determination of the lengths of the shortest path to each possible end state in the trellis, third selection of the end state having the shortest such path and, finally, recreating the original data stream from the selected shortest path by the application of a decoding algorithm. The determination of these shortest paths through the trellis is computationally intensive, typically involving the accumulation of possible shortest paths by comparison of lengths of subsets of all paths, and further comparisons of possible shortest paths to narrow down the selection to the final, shortest path.
A number of designs of encoders and decoders based on convolutional codes such as the Viterbi algorithm, that attempt to reduce the computation time have been proposed and implemented. See, for example, U.S. Pat. No. 5,257,263, entitled "Circuit for Decoding Convolutional Codes for Executing the Survivor Path Storage and Reverse Scanning Stage of a Viterbi Algorithm," which issued on Oct. 26, 1993 to Bazet, et al., and which was assigned to Alcatel Transmission Par Faisceaux Hertziens, as well as U.S. Pat. No. 5,331,665, entitled "Decoder Device for Decoding Convolutionally Encoded Message," which issued on Jul. 19, 1994 to Busschaert, et al., and which was assigned to Alcatel N.V.
One disadvantage of such designs is that they typically involve the use of specialized hardware, for example to optimize the shortest path determinations, which is costly. It would be desirable to use, for example, a general purpose microprocessor or digital signal processor, to perform such determinations in Viterbi encoding and/or decoding. On the other hand, it is desirable to perform such determinations without sacrifice of speed, as compared with specialized hardware. attempt to provide a scheme by which a generalized signal processor might be used to process the Viterbi algorithm is disclosed in U.S. Pat. No. 5,331,664, entitled "Device for Processing the Viterbi Algorithm Comprising a Processor and a Dedicated Operator," which issued on Jul. 19, 1994 to Desperben, et al., and which was assigned to Alcatel Radiotelephone. The scheme disclosed in this patent uses a processor and dedicated operator to perform a Viterbi forward pass. It computes and compares the accumulated distances. The bit result of the comparison is then fed into a shift register. However, it has control modules and registers that are separate from the processor. In addition, a bit is shifted in on each compare. For an n-way Viterbi implementation, n-1 compares are necessary. Thus, n-1 bits are produced, which are more bits than it is desired to be generated.
Therefore, it is desired to have a method and apparatus that allows the performance of the Viterbi algorithm on a general purpose digital signal processor that do not suffer from the aforementioned limitations.
Further, it is desired to have a microprocessor architecture that increases the efficiency of the execution of certain operations found, for example, in Viterbi algorithms, involving manipulation of Boolean values.
The present invention provides these benefits.